class ListItem(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value


class SortSequenceList(object):
    def __init__(self):
        self.SeqList = []

    def CreateSequenceListByInput(self, nElement):
        self.SeqList.append(ListItem(int(0), 0))
        print("请输入数据：")
        for i in range(1, nElement + 1):
            a = input()
            self.SeqList.append(ListItem(int(a), i))

    def TraverseElementSet(self):
        for i in range(1, len(self.SeqList)):
            print(self.SeqList[i].key)

    # 算法8-4 希尔排序方法
    def ShellSort(self):
        SeqListLen = len(self.SeqList)
        Gap = SeqListLen // 2
        while Gap > 0:
            for i in range(Gap + 1, len(self.SeqList)):
                self.SeqList[0].key = self.SeqList[i].key
                j = i - Gap
                while j > 0 and self.SeqList[0].key < self.SeqList[j].key:
                    self.SeqList[j + Gap].key = self.SeqList[j].key
                    j = j - Gap
                self.SeqList[j + Gap].key = self.SeqList[0].key
            Gap = Gap // 2


if __name__ == '__main__':
    SL = SortSequenceList()
    SL.CreateSequenceListByInput(9)
    SL.ShellSort()
    print('希尔排序算法结果为:')
    SL.TraverseElementSet()
